package day003;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Code01_PreInPosTraversal {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data){
            this.value = data;
        }
    }

    public static void travel(Node head){
        if(head == null){
            return;
        }
        System.out.println("A: "+ head.value);
        travel(head.left);
        System.out.println("B: "+head.value);
        travel(head.right);
        System.out.println("C: "+head.value);
    }
    // 先序
    public static void preOrderRecur(Node head){
        if(head == null){
            return;
        }
        System.out.println(head.value + "");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
    // 中序
    public static void inOrderRecur(Node head){
        if(head == null){
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.value);
        inOrderRecur(head.right);
    }
    // 后序
    public static void posOrderRecur(Node head){
        if (head == null){
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.value);
    }

    // 先序遍历 不使用递归
    public static void preOrderUnRecur(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            head = stack.pop();
            System.out.println(head.value);
            if (head.right != null){
                stack.push(head.right);
            }
            if (head.left != null){
                stack.push(head.left);
            }
        }
    }
    // 后续遍历 不使用递归
    public static void posOrderUnRecur(Node head){
        if(head == null){
            return;
        }
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(head);
        while(!stack1.isEmpty()){
            Node cur = stack1.pop();
            stack2.push(cur);

            if(cur.left != null){
                stack1.push(cur.left);
            }
            if(cur.right != null){
                stack1.push(cur.right);
            }
        }
        while(!stack2.isEmpty()){
            System.out.println(stack2.pop().value);
        }
    }
    // 中序遍历 不使用递归
    public static void inOrderUnRecur(Node head){
        if(head == null){
            return;
        }

        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty()
                ||
                head != null){
            if(head != null){  // 以当前为根节点，找到所有左边界节点，依次入栈
                stack.push(head);
                head = head.left;
            }else {
                head = stack.pop();
                System.out.println(head.value);
                head = head.right;  // 对出栈节点的右孩子做同样的操作
            }
        }
    }

    // 宽度遍历
    public static void widthOrder(Node head){
        if(head == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            Node cur = queue.poll(); // 返回头部节点并删除，如果queue为空返回false
            System.out.println(cur.value);

            //先左后右
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }

        }
    }


    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.left = n2;
        n1.right = n3;
        n2.left = new Node(4);
        n2.right = new Node(5);
        n3.left = new Node(6);
        n3.right = new Node(7);

        widthOrder(n1);
    }
}
